package Leetcode;

public class problem287 {
    public static int findDuplicate(int[] nums) {
        int low = 1, high = nums.length - 1;

        while(low <= high)
        {
            int mid = low + (high - low) / 2;
            int cnt = 0;

            for(int a: nums)
            {
                if(a <= mid)
                    cnt++;
            }

            if(cnt <= mid) // meaning duplicate is on the right side
                low = mid + 1;
            else // if cnt > mid, meaning duplicate is on the left side
                high = mid - 1;

        }

        return low;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,3,4,2,2};
        findDuplicate(arr);
    }
}
